package com.echo.boot.structure.heap;

import com.echo.boot.structure.tree.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/6/16
 * Time: 11:04
 * 二叉堆
 *
 * @author Administrator
 */
public class BinaryHeap<E> extends AbstracHeap<E> implements BinaryTreeInfo {
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap() {
        this(null, null);
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }


    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(size, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            // 把 外面的数组元素复制到自己的数组中,防止外面修改
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }


    @Override
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        // 上滤
        siftUp(size - 1);
    }

    /**
     * @author CQ
     * @DESCRIPTION: 让index位置的元素上滤
     * @params: [index] index 索引
     * @return: void
     * @Date: 2020/6/17 15:04
     * @Modified By:
     */
    private void siftUp(int index) {
        E element = elements[index];
        while (index > 0) {
            // i : 当前元素索引,父节点的索引 ： floor((i - 1) / 2);
            // 父节点索引 = floor()
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            // 当前元素 比 父节点 小或者等于 就 break;
            if (compare(element, parent) <= 0) {
                break;
            }
            // 将父元素存储在index位置
            elements[index] = parent;
            // 重新 赋值 index
            index = parentIndex;
        }
        elements[index] = element;
    }

    /**
     * @author CQ
     * @DESCRIPTION: 返回 堆顶元素
     * @params: []
     * @return: E
     * @Date: 2020/6/17 11:06
     * @Modified By:
     */
    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    /**
     * @author CQ
     * @DESCRIPTION: 删除堆顶元素
     * @params: [element]
     * @return: E
     * @Date: 2020/6/13 10:38
     * @Modified By:
     */
    @Override
    public E remove() {
        emptyCheck();
        // 获取最后索引
        int lastIndex = --size;
        // 堆顶
        E root = elements[0];
        // 用最后一个元素 替换 堆顶
        elements[0] = elements[lastIndex];
        // 最后一个置空
        elements[lastIndex] = null;
        // 让对顶元素下滤
        siftDown(0);
        return root;
    }

    /**
     * @author CQ
     * @DESCRIPTION: 让 index 元素位置的元素下滤
     * @params:
     * @return:
     * @Date: 2020/6/17 14:06
     * @Modified By:
     */
    private void siftDown(int index) {
        E element = elements[index];
        // 非叶子节点的数量
        int half = size >> 1;

        //  第一个叶子节点的索引 == 非叶子节点的数量
        // 必须保证index位置是非 叶子节点,才能比较
        // index 必须小于 第一叶子节点

        while (index < half) {
            // index的节点有2中情况
            // 1.只有左子节点
            // 2.同时拥有左右节点
            // 默认 左子节点索引
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }

            // 当前元素 比 子元素大 break;
            if (compare(element, child) >= 0) {
                break;
            }

            elements[index] = child;

            index = childIndex;

        }

        elements[index] = element;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < elements.length; i++) {
            newElements[i] = elements[i];
        }
        System.out.println(oldCapacity + "扩容为 " + newCapacity);
    }

    private void heapify() {
        // 自上而下的上滤
//        for (int i = 1; i < size; i++) {
//            siftUp(i);
//        }

        // 自下而上的下滤
        // (size >> 1) - 1  最后一个非叶子节点
        //
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }


    }

    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("heap is empty");
        }
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index = ((int) node << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = ((int) node << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int) node];
    }
}
